#include <iostream>
#include "SortTestHelper.h"
#include "MergeSort.h"
#include "quickSort.h"
#include "HeapSort.h"


template<typename T>
void __shiftDown(T arr[], int n, int k) {

    T v = arr[k];
    while (2 * k + 1 < n) {

        int j = k * 2 + 1;
        if (j + 1 < n && arr[j + 1] > arr[j]) {
            j += 1;
        }
        if ( v >= arr[j] ) {
            break;
        }
        arr[k] = arr[j];
        k = j;
    }
    arr[k] = v;
}

template<typename T>
void heapSort(T arr[], int n) {


    //heapify
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        __shiftDown(arr, n, i);
    }

    //数组元素在减少
    for (int j = n-1; j > 0; j--) {
        swap(arr[0],arr[j]);
        __shiftDown(arr, j, 0);  //j为未排序堆元素个数
    }

}


int main() {


    int n = 1;
    int swapTime = 10;
    int lMargin = 0;
    int rMargin = n;


    cout << "NearOrderedArray size :" << n << " swapTime : " << swapTime << endl << endl;
    int *arr = SortTestHelper::generateNearOrderedArray(n, swapTime);

//    cout<<"origin array : ";
//    SortTestHelper::printArray(arr,n);
//    cout<<endl;

    int *arr1 = SortTestHelper::copyIntArray(arr, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    int *arr3 = SortTestHelper::copyIntArray(arr, n);
    int *arr4 = SortTestHelper::copyIntArray(arr, n);
    int *arr5 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("merge sort", mergeSort, arr, n);
    SortTestHelper::testSort("merge sort beat", mergeSortBeat, arr1, n);
    SortTestHelper::testSort("quick sort3Ways", quickSort3Ways, arr2, n);
    SortTestHelper::testSort("heap sort 1", heapSort1, arr3, n);
    SortTestHelper::testSort("heap sort 2", heapSort2, arr4, n);
    SortTestHelper::testSort("heap sort 3", heapSort, arr5, n);

    //清除new开辟的内存空间，防止内存泄漏
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    cout << endl;


    cout << "RandomArray size :" << n << "  left margin : " << lMargin << "  right margin : " << rMargin << endl;
    arr = SortTestHelper::generateRandomArray(n, lMargin, rMargin);

//    cout<<"origin array : ";
//    SortTestHelper::printArray(arr,n);
//    cout<<endl;

    arr1 = SortTestHelper::copyIntArray(arr, n);
    arr2 = SortTestHelper::copyIntArray(arr, n);
    arr3 = SortTestHelper::copyIntArray(arr, n);
    arr4 = SortTestHelper::copyIntArray(arr, n);
    arr5 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("merge sort", mergeSort, arr, n);
    SortTestHelper::testSort("merge sort beat", mergeSortBeat, arr1, n);
    SortTestHelper::testSort("quick sort3Ways", quickSort3Ways, arr2, n);
    SortTestHelper::testSort("heap sort 1", heapSort1, arr3, n);
    SortTestHelper::testSort("heap sort 2", heapSort2, arr4, n);
    SortTestHelper::testSort("heap sort 3", heapSort, arr5, n);

    //清除new开辟的内存空间，防止内存泄漏
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    cout << endl;

    lMargin = 0;
    rMargin = 10;
    cout << "RandomArray size :" << n << "  left margin : " << lMargin << "  right margin : " << rMargin << endl;
    arr = SortTestHelper::generateRandomArray(n, lMargin, rMargin);

//    cout<<"origin array : ";
//    SortTestHelper::printArray(arr,n);
//    cout<<endl;

    arr1 = SortTestHelper::copyIntArray(arr, n);
    arr2 = SortTestHelper::copyIntArray(arr, n);
    arr3 = SortTestHelper::copyIntArray(arr, n);
    arr4 = SortTestHelper::copyIntArray(arr, n);
    arr5 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("merge sort", mergeSort, arr, n);
    SortTestHelper::testSort("merge sort beat", mergeSortBeat, arr1, n);
    SortTestHelper::testSort("quick sort3Ways", quickSort3Ways, arr2, n);
    SortTestHelper::testSort("heap sort 1", heapSort1, arr3, n);
    SortTestHelper::testSort("heap sort 2", heapSort2, arr4, n);
    SortTestHelper::testSort("heap sort 3", heapSort, arr5, n);

    //清除new开辟的内存空间，防止内存泄漏
    delete[] arr;
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    cout << endl;

    return 0;
}